package com.fufu.algorithem.stack;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式转后缀表达式
 * @author: BlcakTiger
 * @date: 2023/2/14 20:38
 * @contact: hsf6661@163.com
 */
public class InFixToSuffix {

    public static void main(String[] args) {
        //定义中缀表达式 1+2*3-4 => suffix  1 2 3 * + 4 -  res=3
        //two:(1+3)*2-5/5  ==>  "1 3 + 2 - 5 * 5 /" 等价 "1 3 + 2 * 5 5 / -"   res=7
        //inFixExpression = "1+((2+3)*4)-5"; 另一个例子
        //创建一个中缀表达式
        String inFixExpression = "(1+3)*2-5/5";
        //对表达式进行格式化
        inFixExpression = trimFormat(inFixExpression);
        //将中缀表达式转换为后缀表达式
        String suffix = toSuffix(inFixExpression);
        //调用之前逆波兰计算器
        double res = RPN.reversePolishCalculator(suffix);

        System.out.println("After formatting:"+inFixExpression);
        System.out.println("infix:" + inFixExpression);
        System.out.println("suffix:" + suffix);
        System.out.println("res:" + res);
    }

    /**
     * 将前缀表达式转换为后缀表达式
     *
     * @param inFix 前缀表达式
     * @return 后缀表达式
     */
    public static String toSuffix(String inFix) {
        List<String> inFixList = Arrays.asList(inFix.split(" "));
        Stack<String> stack = new Stack<>();
        StringBuilder suffix = new StringBuilder();
        String po_regex = "\\d+";
        String mi_regex = "-\\d+";
        String pofRegex = "\\d+.\\d+";
        String mifRegex = "-\\d+.\\d+";
        for (String s : inFixList) {
            //如果是数字，直接拼接到后缀字符串上
            if (s.matches(po_regex) || s.matches(mi_regex) || s.matches(pofRegex) || s.matches(mifRegex)) {
                suffix.append(s + " ");
            } else if ("(".equals(s)) {
                stack.push(s);
            } else if (")".equals(s)) {
                while (true) {
                    if ("(".equals(stack.peek())) {
                        //将"("弹出舍弃
                        stack.pop();
                        break;
                    }
                    suffix.append(stack.pop() + " ");
                }
            } else {//如果是操作符：
                //1.如果当前栈为空：符号直接入栈
                if (stack.isEmpty()) {
                    stack.push(s);
                } else {
                    //2.如果不为空：与栈顶操作符做比较，当前符号优先级低于栈顶，取出栈顶操作符拼接到后缀字符串，并将当前字符入栈
                    //补充：对于相同优先级的操作符，哪个先执行都ok，因为不会影响结果，所以这里既可以带上==，也可以不带
                    //根据选择的不同最终获取的后缀表达式也会不同，但这二个后缀表达式计算的结果都是一样的
                    if (priority(s) <= priority(stack.peek())) {
                        suffix.append(stack.pop() + " ");
                        stack.push(s);
                    } else {
                        stack.push(s);
                    }
                }
            }
        }

        //将栈中剩余的操作符依次pop出并追加到suffix
        while (!stack.isEmpty()) {
            suffix.append(stack.pop() + " ");
        }
        return suffix.toString();
    }

    /**
     * 返回操作符的优先级
     *
     * @param op 操作符
     * @return 若返回-1表示符号错误
     */
    public static int priority(String op) {
        if ("+".equals(op) || "-".equals(op)) {
            return 1;
        } else if ("*".equals(op) || "/".equals(op)) {
            return 2;
        } else {
            return -1;
        }
    }

    /**
     * 去掉original两端及里面的空白符并格式化字符串,如：" "、'\t'、'\n'
     *
     * @param original 原先的字符串
     * @return 修剪后的字符串
     */
    public static String trimFormat(String original) {
        //初始化一个可变字符串
        StringBuilder trimed = new StringBuilder();
        for (int i = 0; i < original.length(); i++) {
            if (original.charAt(i) == ' ' || original.charAt(i) == '\t' || original.charAt(i) == '\n') {
                continue;
            }
            trimed.append(original.charAt(i));
        }
        String str = trimed.toString();
        String temp = "";
        char ch;
        trimed.delete(0, trimed.length());
        for (int i = 0; i < str.length() - 1; i++) {
            ch = str.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')') {
                trimed.append(ch + " ");
            } else {
                //优化表达式
                if (((ch + "").matches("\\d") || ch == '.') && (str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9' || str.charAt(i + 1) == '.')) {
                    temp += str.charAt(i);
                } else {
                    temp += str.charAt(i);
                    trimed.append(temp + " ");
                    temp = "";
                }
            }
        }
        //因为每次循环为了能够查看到一个数的下一位是否也是数字，所以在循环时需要减少1次
        //故而遍历结束后表达式还有一个末尾的数没有拼接到trimed中
        trimed.append(str.charAt(str.length() - 1));

        return trimed.toString();
    }
}

